package com.fs.leetcode.paixu;

import java.util.Arrays;

/**
 * @author huyunqiang
 * @Date 2020/6/8 20:21
 */
public class InsertSort {

    public static void insertSort(int[] arr){

//        int insertVal = arr[1];
//        //要和前一个数进行比较
//        int insertindex = 1-1;
//        //找indexVal 插入的位置
//        while(insertindex >= 0 && arr[insertindex] > insertVal){
//            //还么有找到 移动前面的元素向后移动一位
//            arr[insertindex+1] = arr[insertindex];
//            insertindex --;
//
//        }
//        //推出循环说明已经找到位置  将该元素插入到前一个元素后面
//        arr[insertindex+1] = insertVal;
//        System.out.println("第yi轮排序后"+Arrays.toString(arr));

        for (int i=1;i<arr.length;i++){
            //第一个元素已经是有序，所有从第二个元素开始
            int insertVal = arr[i];
            //定义移动执政，要和前一个数进行比较
            int insertindex = i-1;
            //找indexVal 插入的位置
            while(insertindex >= 0 && arr[insertindex] > insertVal){
                //还么有找到 移动前面的元素向后移动一位
                arr[insertindex+1] = arr[insertindex];
                insertindex --;

            }
            //推出循环说明已经找到位置  将该元素插入到前一个元素后面
            arr[insertindex+1] = insertVal;
            System.out.println("第"+i+"轮排序后"+Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = {99, 44, 38, 5, 47, 15};
        insertSort(arr);

    }
}
